package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * <p>
 * dp
 * 576. 出界的路径数
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/13 13:28
 */
public class FindPaths {

    public static void main(String[] args) {
        FindPaths test = new FindPaths();

        // 25  25  37   791571587
//        int m = 48;
//        int n = 49;
//        int maxMove = 25;
//        int startRow = 25;
//        int startColumn = 37;

        //    5245392
//        int m = 50;
//        int n = 50;
//        int maxMove = 50;
//        int startRow = 25;
//        int startColumn = 37;

        //    6
//        int m = 2;
//        int n = 2;
//        int maxMove = 2;
//        int startRow = 0;
//        int startColumn = 0;

        //    4
        int m = 1;
        int n = 1;
        int maxMove = 50;
        int startRow = 0;
        int startColumn = 0;

        // m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1   12
//        int m = 1;
//        int n = 3;
//        int maxMove = 3;
//        int startRow = 0;
//        int startColumn = 1;

        int paths = test.findPaths(m, n, maxMove, startRow, startColumn);
        System.out.println(paths);
    }


    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        long[][][] arr = new long[m][n][maxMove + 1];
        for (int k = 1; k <= maxMove; k++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    long sum = 0;
                    sum += i == 0 ? 1 : arr[i - 1][j][k - 1];
                    sum += j == 0 ? 1 : arr[i][j - 1][k - 1];
                    sum += i == m - 1 ? 1 : arr[i + 1][j][k - 1];
                    sum += j == n - 1 ? 1 : arr[i][j + 1][k - 1];
                    arr[i][j][k] = sum % 1000000007;
                }
            }
        }
        return (int) (arr[startRow][startColumn][maxMove] % 1000000007);
    }


}
